/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-02-17
 * Time:12:11
 */

/**
 * 688. 骑士在棋盘上的概率
 * 在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，
 * 并尝试进行 k 次移动。行和列是 从 0 开始 的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。
 * 象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。
 * 每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。
 * 骑士继续移动，直到它走了 k 步或离开了棋盘。
 * 返回 骑士在棋盘停止移动后仍留在棋盘上的概率
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/knight-probability-in-chessboard
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 **/
public class TestDemo {
    public static int[][] dirs = {{-1, -2}, {-1, 2}, {-2, -1}, {-2, 1}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};
    public static int[][] nums;
    public static int step;

    //dfs-深度优先搜索算法 ->会超时
    public static double knightProbability1(int n, int k, int row, int column) {
        double sum = Math.pow(8, k);
        nums = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                nums[i][j] = 0;
            }
        }
        nums[row][column] = 1;
        dfs(nums, row, column, k);
        return (step) / sum;
    }

    public static void dfs(int[][] nums, int row, int column, int k) {
        if (row < 0 || row >= nums.length || column < 0 || column >= nums.length || k < 0) {
            return;
        }
        k--;
        //当达到步数上限时,静态的step就加加
        if (k == -1) {
            step++;
            return;
        }
        //向8个方向进行前进
        for (int[] a : dirs) {
            dfs(nums, row + a[0], column + a[1], k);
        }
    }

    public static void main(String[] args) {
        int n = 8, k = 30, row = 6, column = 4;
        System.out.println(knightProbability(n, k, row, column));
    }
    //动态规划
    //当前算法是算出每一个位置走的所有步数的概率;最后输出你要找的位置以及步长就可以得到答案
    //例如 n = 3, k = 2, row = 0, column = 0
    //建立3*3*2的三维数组 第一层存的全是1
    //[0][0][1]存储的是 [0][0]这个位置走1步后仍在棋盘上的概率
    //[0][0][2]存储的是 [0][0]这个位置走2步后仍在棋盘上的概率
    //[0][0][1] = [0][0]走一步仍在棋盘上的情况 / 8种步数情况; [0][0][1]=2/8 = 1/4;
    /**
     * 输入: n = 3, k = 2, row = 0, column = 0
     *     输出: 0.0625
     *     解释: 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。
     *     在每一个位置上，也有两种移动可以让骑士留在棋盘上。
     *     骑士留在棋盘上的总概率是0.0625*/

    public static double knightProbability(int n, int k, int row, int column) {
        //三维数组,第一层存储的全是1;第2层[i][j][1]存储的是由[i][j]出发并且走1步后仍然在棋盘上的概率
        //第3层[i][j][2]存储的是由[i][j]出发走2步后仍然在棋盘上的概率
        double[][][] f = new double[n][n][k + 1];
        //将第一层全填上1
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                f[i][j][0] = 1;
            }
        }
        //遍历数组
        for (int p = 1; p <= k; p++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int[] d : dirs) {
                        int nx = i + d[0], ny = j + d[1];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
                            continue;
                        }
                        //因为有8个方向,所以每次走了一步后还存在棋盘上的概率是
                        //当前[i][j][p]的概率*八分之一;
                        f[i][j][p] += f[nx][ny][p - 1] / 8;
                    }
                }
            }
        }
        return f[row][column][k];
    }
}
